This invention relates to systems for sorting mail items and to related techniques for generating ordered lists and searching on such lists. More particularly, the invention relates to method and apparatus which facilitates selective outsorting or other selective custom remapping or sorting of mail items contained in a mass mailing, including improved search techniques usable therewith.
Many organizations perform mass mailings of post cards, letters, catalogs, magazines, packages or other mail items on a daily basis. Such mailings can frequently exceed a million items per day. However, for many such mailings, there are a significant percentage of items which need not be sent, and in some instances should not be sent. For example, many such mailings include notices that a subscription, insurance policy or the like is about to be cancelled or has been cancelled for nonpayment of a renewal fee, premium or the like or other dunning letter for nonpayment of amounts due. Since there is normally a delay of several days, for example three to five days, between the time action is taken to initiate the sending of such a letter and the time the letter is actually mailed, in a significant percentage of cases, perhaps 3-10 percent of the cases depending on the industry, payment has been received before the letter actually goes out. Since there is a cost of approximately 25 cents in postage alone for the sending of such a letter, and the receipt of such a letter can engender bad will on the part of the recipient and cost the sender additional money in customer relations personnel having to deal with a concerned or irate customer, it is desirable to purge such notices from a mailing. However, a system for quickly and easily performing such a purge does not currently exist.
Similarly, a potential problem for a charity, catalog company or other company doing a mass mailing for solicitation, advertising or related purposes to recipients whose names have been obtained from a variety of mailing lists, is that multiple items are frequently sent to the same recipient. The mailer may be unaware of the problem since a recipient may appear as John Doe on one list, J. Doe on a second list, Mr. and Mrs. John Doe on a third list, John and Jane Doe on a fourth list, etc. Such multiple mailings to a single recipient are undesirable both because of the cost, both postage costs and the cost of the catalog or other material being sent, and because receiving multiple copies of the same mailing is annoying to the recipient and reflects badly on the organization and competence of the sender. Therefore, it would be desirable if such multiple copies could be purged so that a given recipient receives only one, or at most two, copies of the mailing. However, a technique for easily and inexpensively accomplishing this objective does not currently exist.
Other situations also exist where some type of custom purge, custom sorting and/or remapping is desirable on a given mailing. For example, where an international mailing is to be sorted by a system which handles only numeric characters, alpha-numeric postal codes for some countries may need to be remapped to for example a numeric code for the country before application to the sorting equipment. There are also applications where a variety of programmable data manipulations, configurable outsorting of mail items, or various types of selective sorting of mail may be required or otherwise desirable or where it is desirable to perform statistical modeling, trend analysis, frequency distribution or other analysis on mail items being sent. While some of the these functions can be performed at a main computer of the mailing organization before mail items are addressed and sorted for mailing, this does not provide information on mail items actually sent, and may therefore be less accurate than collecting information as the mail items are being sorted for delivery to the post office. Such a procedure also permits errors which have not been caught and corrected earlier in the system to still be corrected before the mailing goes out, for example to pick up a recently received change of address. Further, it would be desirable if such objectives could be accomplished without requiring any changes to existing sorting systems and without requiring reprogramming of the computers used to currently control such sort operations. None of the above capabilities currently exist.
While the various operations indicated above could be performed by receiving an entire postal code for each mail item, and then performing matches or other operations on each such received code in order to effect the desired purge/re-mapping function, current sorting systems for mail items operate at very high speed, for example approximately twelve mail items per second for an illustrative system, in order to permit optimum utilization of available sort equipment. It is important that any method and apparatus for accomplishing the various functions discussed above not have a significant adverse impact on system throughput. Since postal code characters are received in a typical sorting system one character at a time, a procedure which permits characters to be matched on as received, rather than waiting for the entire postal code to be read and received, could permit desired operations to be performed, and in many cases completed, while the characters are being received, thereby resulting in substantially no delay as a result of these operations, and could significantly reduce any delays resulting from operations which can only be completed after all characters are received, thereby permitting the various operations indicated above to be performed with negligible impact on system throughput. Similar problems can arise in other applications, for example some artificial intelligence applications, where data is received piecemeal, generally a character at a time, and particularly where decisions may need to be made before all data is received. However, existing techniques for storing ordered lists or for searching on such lists do not normally permit such searching to be performed, character by, character as, characters are being received. A need therefore exists for an improved ordered list storage and searching technique for facilitating such character-by-character searching.
In accordance with the above, this invention provides a method and apparatus for use in a system utilizing a sort processor to sort mail items based on an N character postal code read from each mail item by a code reader, the apparatus operating to facilitate the custom sorting, outsorting or other re-mapping of mail items from a mailing. The apparatus includes a memory storing a listing of postal codes for which mail items are, for example to be custom sorted or outsorted; and a processor to which outputs from the code reader are applied, the processor searching for matches between codes applied thereto and codes stored in the listing, passing selected outputs to the sort processor in response to matches found for selected mail items, and passing different selected outputs to the sort processor for mail items on which no match is found. Where no match is found, the postal code may for example be passed unaltered to the sort processor, while if a match is found, a defined value may be passed to the sort processor. The sort processor may respond to the defined value by outsorting the corresponding mail item. Alternatively, if no match is found, a defined value may be passed to the sort processor. The defined value may be a defined count value or a defined forced output value. A forced output value for each stored postal code may for example be stored in the list with the corresponding code. The sort processor may respond to a defined value by outsorting the corresponding mail item.
For other embodiments, if a match is found, a selected action is taken as a function of at least one stored condition. For example, the number of matches in a sort for a given stored postal code may be stored in the listing with the postal code, and the selected action for a given postal code may be taken as a function of the number of prior matches for such code. For a preferred embodiment, the postal code has a sufficient number of characters to uniquely identify individual address locations. In particular, the items to be custom sorted may be mail items to be purged from a mailing, the list containing, for example, 11-digit ZIP codes for such items, and the processor passing ZIP codes read by the processor to the sort processor when there is no match, and passing a defined ZIP code to the sort processor when there is a match, the defined ZIP code causing the sort processor to outsort the corresponding mail items. For another embodiment, the list contains all postal codes in the mailing and a count of the number of matches for each postal code. The processor increments the count for a postal code each time a match is found, and the processor causes outsorting of an item coded for a given postal code if the count for the postal code is at least a selected value. For one embodiment, the selected value is 1.
The stored list may be an ordered list of the N character postal codes, the code reader applying characters sequentially to the processor as read, and the processor matching on each subset of M of the characters as received, terminating the match attempt for an item when a match is not found at a point in the search, and passing a xe2x80x9cno matchxe2x80x9d output to the sort processor for such items. Match attempts for a received subset for a given item are preferably performed starting at a point in the ordered list determined by matches on the prior received subset for the item. The ordered list preferably includes an N bit representation of each character of each entry, there being a node in the memory corresponding to each bit, and the bits of each entry being linked to form a tree. The processor converts characters outputted from the reader to the N bit representation and uses these bits to search in the tree until an empty node is found, signifying a mismatch, or an end of search indication is received.
For preferred embodiments, the postal codes are bar codes, and the code reader is a bar code reader (BCR), while for an alternative embodiment, the postal code is in optical character form, and the code reader is an optical character reader (OCR). Where the postal codes are N character bar codes and the list is an ordered list of N character bar codes, the code reader may apply the characters sequentially to the processor and the processor may match on each subset of M of the characters as received, terminate the match attempt for an item when a match is not found for a subset, and pass a xe2x80x9cno matchxe2x80x9d output to the sort processor for such items.
The invention also includes, in a system for utilizing a sort processor to sort mail items based on an N digit postal code read from each item by a code reader, an apparatus for facilitating selective custom sorting of at least selected ones of the mail items, which apparatus includes a memory storing a list of postal codes for items to be custom sorted; and a processor to which code reader output characters are sequentially applied as read, the processor searching for matches between each subset of M of the digits of each incoming postal code as received and postal codes in the list, terminating match searching for a mail item when a match is not found at any point in the search for the item or when all desired characters have been searched and, on termination of match searching for an item, passing a selected output to the sort processor in response to a match being found and a different selected output to the sort processor in response to no match being found. For this aspect of the invention, match attempts for a received subset for a given mail item are preferably performed starting at a point in the ordered list determined by matches on the prior received subset for the item.
In accordance with still another aspect of the invention, a method and apparatus for remapping of mail items of a mailing are provided which include a memory storing a listing of postal codes for which remapping of mail items should be performed; and a control processor to which outputs from the code reader are applied, the control processor searching for matches between codes applied thereto and codes stored in the listing, passing selected outputs to the sort processor in response to matches found for selected mail items under selected conditions, and passing different selected outputs to the sort processor for mail items where (i) no matches are found and/or (ii) matches are found under different conditions. In the method and apparatus indicated above, the control processor can also be utilized to collect and/or report data on matches performed, perform statistical modeling, trend analysis, frequency distributions and/or other analysis on the mailing.
In accordance with still another aspect of the invention, a method and apparatus are provided for storing an ordered list of multicharacter entries in a memory device which includes converting each character of each entry into an N bit representation of the character by use of a suitable mechanism and which combines the N bit representations in a predetermined order to form an incremental ordered entry (IOE); and, starting at a selected node in the memory device, utilizing a suitable mechanism to look at a first bit of the IOE, branch to a node in a first direction if the bit is a zero, branch to a node in a second direction if the bit is a one, determine if an entry is stored at the node branched to and store a selected entry at the node branched to if it does not already contain an entry, this sequence of operations being repeated for each successive bit of the IOE, starting for each bit at the node branched to for the preceding bit of the IOE, until all bits of the IOE have been looked at. The predetermined order may, for example, be from most significant bit of the most significant character to least significant bit of the least significant character. The successive nodes for each IOE form a tree branch, at least selected nodes on each tree branch containing at least a representation of the IOE characters to that point in the tree branch. At least selected nodes may also contain data to be outputted in the event a search were to end at the node, and at least selected ones of the nodes may be shared by tree branches for at least two IOE entries.
A method and apparatus may also be provided for performing a search to determine if a multicharacter input received a character at a time matches in entry in an ordered list of multicharacter entries stored in a memory device in accordance with the method and apparatus indicated above. Such method and apparatus convert each character of the multicharacter input as received into an N bit representation of the character; and then utilize a suitable mechanism to look at the bits for the input characters in a predetermined order, M characters at a time, where M is an integer xe2x89xa71, starting at the selected node, and branching to a node in a first direction if the bit looked at is a zero, branching to a node in the second direction if the bit looked at is a one, continuing the branching for a successive bit if there is an entry at the node branched to, and generating a xe2x80x9cno matchxe2x80x9d indication if there is no entry at the node branched to N bit representations of successive characters of the input being looked at until either a xe2x80x9cno matchxe2x80x9d indication is generated or an end of search indication is received. Looking at bits for each M characters of the input after the first M characters preferably starts at the node at which looking for the last bit of the preceding M characters looked at ended. The end of search indication may, for example, be an end of entry input received at the end of the input entry or a signal generated by a suitable mechanism at a selected point of the input. In response to an end of search indication, suitable mechanisms may be provided for utilizing the entry at the last node branched to before the end of search indication to perform a selected control function.
The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention as illustrated in the accompanying drawings.